import collections


class Solution(object):
    def shoppingOffers(self, price, special, needs):
        """
        :type price: List[int]
        :type special: List[List[int]]
        :type needs: List[int]
        :rtype: int
        """
        n = len(price)
        m = len(special)
        self.min_price = sum([price[i] * needs[i] for i in range(n)])
        first = tuple([0 for _ in range(n)])
        prefix = collections.defaultdict(int)
        prefix[first] = 0

        def cal_price(s, p):
            flag = True
            count = 0
            for i in range(n):
                if s[i] <= needs[i]:
                    if s[i] == needs[i]:
                        count += 1
                    else:
                        p += (needs[i] - s[i]) * price[i]
                else:
                    flag = False
                    break
            if flag:
                self.min_price = min(self.min_price, p)
                if count == n:
                    flag = False
            return flag

        def add(t1, t2, k):
            new = [0] * n
            for i in range(n):
                new[i] = t1[i] + t2[i] * k
            return tuple(new)

        for i in range(m):
            next_prefix = collections.defaultdict(int)
            for pre in prefix:
                if pre in next_prefix:
                    next_prefix[pre] = min(prefix[pre], next_prefix[pre])
                else:
                    next_prefix[pre] = prefix[pre]
                k = 1
                while True:
                    new = add(pre, special[i], k)
                    new_price = prefix[pre] + k * special[i][-1]
                    if cal_price(new, new_price):
                        if new in next_prefix:
                            next_prefix[new] = min(next_prefix[new], new_price)
                        else:
                            next_prefix[new] = new_price
                        k += 1
                    else:
                        break
            prefix = next_prefix
        return self.min_price


data = Solution()
# price = [2, 5]
# special = [[3, 0, 5], [1, 2, 10]]
# needs = [3, 2]
# print(data.shoppingOffers(price, special, needs))
# price = [2, 3, 4]
# special = [[1, 1, 0, 4], [2, 2, 1, 9]]
# needs = [1, 2, 1]
# print(data.shoppingOffers(price, special, needs))
price = [2, 3]
special = [[1, 0, 1], [0, 1, 2]]
needs = [1, 1]
print(data.shoppingOffers(price, special, needs))
